import java.util.HashSet;
import java.util.Set;

//环形链表2：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。
//为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
// 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
//说明：不允许修改给定的链表。
//进阶：
//你是否可以使用 O(1) 空间解决此题？
//输入：head = [3,2,0,-4], pos = 1
//        输出：返回索引为 1 的链表节点
//        解释：链表中有一个环，其尾部连接到第二个节点。
public class leetcode_142 {
    //哈希表：一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；
    // 一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。
    public ListNode detect6Cycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}